#pragma once
using namespace std;

namespace linhui
{
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{ 53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	template<class T>
	struct HashData
	{
		HashData(const T& input = T())
			:_item(input)
			, _next(nullptr)
		{

		}
		T _item;
		HashData* _next;
	};

	/*template<class T>
	struct HashFunc
	{
		size_t operator()(const T& item)
		{
			return item;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& item)
		{
			size_t ret = 0;
			for (const auto& au : item)
			{
				ret += au;
				ret *= 131;
			}
			return ret;
		}
	};*/
	template<class T , class Ptr , class Ref , class KeyOfVal , class HashFunc>
	class Iterator
	{
	public:
		using Data = HashData<T>;

		Iterator(Data* self = Data(),vector<Data*> table = vector<Data*>())
			:_self(self)
			,_table(table)
		{

		}

		Iterator operator++()
		{
			HashFunc hfc;
			KeyOfVal kov;
			size_t hashKey = hfc(kov(_self->_item)) % _table.size();
			if (_self->_next != nullptr)
			{
				_self = _self->_next;
			}
			else
			{
				hashKey += 1;
				while (hashKey < _table.size() && _table[hashKey] == nullptr)
				{
					hashKey += 1;
					if (hashKey >= _table.size())
					{
						_self = nullptr;
						return { nullptr,_table };
					}
				}
				_self = _table[hashKey];
			}
			return _self;
		}

		Ref operator*()
		{
			return _self->_item;
		}

		Ptr operator->()
		{
			return &_self->_item;
		}
		
		bool operator!=(Iterator _right)
		{
			return _self != _right._self;

		}

		Data* _self;
		vector<Data*> _table;
	};


	template<class Key, class Val,class KeyOfVal, class HashFunc>
	class HashTable
	{
	public:
		using Data = HashData<Val>;
		//about iterator
		using iterator = Iterator<Val, Val*, Val&, KeyOfVal, HashFunc>;
		using const_iterator = Iterator<Val, const Val*,const Val&, KeyOfVal, HashFunc>;
		iterator begin()
		{
			if (_size == 0)
				return { nullptr , _table};
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
					return { _table[i] , _table};
			}
		}
		iterator end()
		{
			return { nullptr , _table };
		}
		//constructor
		HashTable()
			:_table(11, nullptr)
			,_size(0)
		{
		}
		//destructor
		~HashTable()
		{
			if (_size > 0)
			{
				for (int i = 0; i < _table.size(); i++)
				{
					if (_table[i] != nullptr)
					{
						Data* cur = _table[i];
						while (cur != nullptr)
						{
							Data* next = cur->_next;
							delete cur;
							cur = next;
						}
						_table[i] = nullptr;
					}
				}
			}
		}
		//copy-constructor
		HashTable(const HashTable& obj)
			:_table(11, nullptr)
			,_size(0)
		{
			if (obj._size > 0)
			{
				for (int i = 0; i < obj._table.size(); i++)
				{
					if (obj._table[i] != nullptr)
					{
						Data* cur = obj._table[i];
						while (cur)
						{
							HashFunc hfc;
							int hashKey = hfc(cur->_item) % (obj._table.size());
							Insert(cur->_item);
							cur = cur->_next;
						}
					}
				}
			}
		}
		//assign operator reload
		void operator=(HashTable obj)
		{
			if (_table != obj._table)
			{
				std::swap(_table, obj._table);
				std::swap(_size, obj.size);
			}
		}
		//insert
		pair<iterator,bool> Insert(const Val& input)
		{
			//avoid com
			KeyOfVal kov;
			auto ret = Find(kov(input));
			if (ret != nullptr)
			{
				return {ret,false};
			}
			//calculate load factor and malloc
			if (_size >= _table.size())
			{
				vector<Data*> newTable;
				newTable.resize(__stl_next_prime(_table.size() + 1));
				for (int i = 0; i < _table.size(); i++)
				{
					if (_table[i] != nullptr)
					{
						Data* cur = _table[i];
						while (cur != nullptr)
						{
							HashFunc hfc;
							KeyOfVal kov;
							int hashKey = hfc(kov(cur->_item)) % (newTable.size());
							Data* next = cur->_next;
							cur->_next = newTable[hashKey];
							newTable[hashKey] = cur;

							cur = next;
						}
					}
				}
				_table.swap(newTable);
			}
			//ensure balance factor and insert
			HashFunc hfc;
			int hashKey = hfc(kov(input)) % (_table.size());
			Data* newNode = new Data(input);
			Data* next = _table[hashKey];
			_table[hashKey] = newNode;
			newNode->_next = next;
			_size++;
			return { {newNode,_table},true};
		}
		//find
		iterator Find(Key key)
		{
			HashFunc hfc;
			KeyOfVal kov;
			int hashKey = hfc(key) % _table.size();
			Data* cur = _table[hashKey];
			while (cur != nullptr)
			{
				if (kov(cur->_item) == key)
					return cur;
				cur = cur->_next;
			}
			return { nullptr , _table};
		}
		//count
		size_t Count(Key key)
		{
			HashFunc hfc;
			KeyOfVal kov;
			int hashKey = hfc(key) % _table.size();
			Data* cur = _table[hashKey];
			int ret = 0;
			while (cur != nullptr && kov(cur->_item) == key)
			{
				ret += 1;
				cur = cur->_next;
			}
			return ret;
		}
		//erase
		bool Erase(Key key)
		{
			HashFunc hfc;
			size_t hashKey = hfc(key) % _table.size();
			Data* cur = _table[hashKey];
			if (_table[hashKey] != nullptr)
			{
				Data* prev = nullptr;
				while (cur)
				{
					if (cur->_item == key)
					{
						if (prev == nullptr)
						{
							Data* next = cur->_next;
							_table[hashKey] = next;
						}
						else
						{
							prev->_next = cur->_next;
						}
						delete cur;
						return true;
					}
					prev = cur;
					cur = cur->_next;
				}
				_size -= 1;
				return true;
			}
			return false;
		}
		size_t size() const
		{
			return _size;
		}
	private:
		vector<Data*> _table;
		size_t _size;

	};


}